package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * back
 * LCP 45. 自行车炫技赛场
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/14 15:22
 */
public class BicycleYard {

    public static void main(String[] args) {
        BicycleYard test = new BicycleYard();

        // {{0,1},{1,0},{1,1}}
//        int[] position = {0, 0};
//        int[][] terrain = {{0, 0}, {0, 0}};
//        int[][] obstacle = {{0, 0}, {0, 0}};

        // {{0,1}}
//        int[] position = {1, 1};
//        int[][] terrain = {{5, 0}, {0, 6}};
//        int[][] obstacle = {{0, 6}, {7, 0}};

        // [[0,3],[0,6],[0,8],[2,8],[3,8],[4,6]]
        int[] position = {0, 1};
        int[][] terrain = {{63, 91, 53, 6, 70, 29, 1, 86, 31}, {0, 42, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 74, 77, 94, 8}, {55, 57, 59, 0, 0, 0, 11, 33, 23}, {58, 27, 51, 0, 0, 56, 10, 24, 7}, {82, 49, 74, 0, 0, 79, 96, 68, 25}, {72, 51, 67, 0, 58, 59, 81, 52, 64}, {95, 30, 35, 0, 45, 79, 71, 15, 74}};
        int[][] obstacle = {{21, 7, 31, 16, 33, 39, 25, 12, 4}, {0, 42, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 19, 14, 43, 30}, {50, 8, 37, 0, 0, 0, 44, 33, 17}, {5, 12, 29, 0, 0, 30, 2, 33, 40}, {40, 18, 14, 0, 0, 24, 15, 6, 19}, {10, 3, 40, 0, 39, 38, 16, 44, 48}, {48, 27, 26, 0, 42, 13, 9, 25, 31}};

        // {{0,1}}
//        int[] position = {5, 5};
//        System.out.println(Arrays.toString(position));
//        int[][] terrain = Utils.getArr(100, 100, 0, 30);
//        int[][] obstacle = Utils.getArr(100, 100, 0, 30);

        int[][] ints = test.bicycleYard(position, terrain, obstacle);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    public int[][] bicycleYard(int[] position, int[][] terrain, int[][] obstacle) {
        int m = terrain.length;
        int n = terrain[0].length;
        int l = m * n;
        List<Integer>[] lists = new ArrayList[l];
        int x = position[0];
        int y = position[1];
        List<Integer> list = new ArrayList<>();
        list.add(1);
        lists[x * n + y] = list;
        LinkedList<Integer> q = new LinkedList<>();
        q.add((x << 24) + (y << 16) + 1);
        List<Integer> values = new ArrayList<>();

        int[][] arr = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        while (!q.isEmpty()) {
            int poll = q.poll();
            x = poll >> 24;
            y = (poll >> 16) & 0XFF;
            int c = poll & 0XFFFF;
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || a == m || b < 0 || b == n) {
                    continue;
                }
                int d = c + terrain[x][y] - terrain[a][b] - obstacle[a][b];
                if (d < 1) {
                    continue;
                }
                List<Integer> nextList = lists[a * n + b];
                if (nextList == null) {
                    nextList = new ArrayList<>();
                    lists[a * n + b] = nextList;
                }
                if (nextList.contains(d)) {
                    continue;
                }
                if (d == 1) {
                    values.add((a << 16) + b);
                }
                nextList.add(d);
                q.add((a << 24) + (b << 16) + d);
            }
        }
        Collections.sort(values);
        int size = values.size();
        int[][] vs = new int[size][2];
        for (int i = 0; i < size; i++) {
            int t = values.get(i);
            vs[i][0] = t >> 16;
            vs[i][1] = t & 0XFFFF;
        }
        return vs;
    }


}
